package com.leetcode.algorithm.y19.m11;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 
 * (done)1051. 高度检查器
 * (done)1089. 复写零
 * (done)1122. 数组的相对排序
 * (done)1128. 等价多米诺骨牌对的数量
 * (done)1170. 比较字符串最小字母出现频次
 * 
 * @author jie.deng
 * @time 2019年11月28日 上午9:38:20
 */
public class MySolution1128 {
	/**
	 * (done)1051. 高度检查器
	 * 
	 * 学校在拍年度纪念照时，一般要求学生按照 非递减 的高度顺序排列。
	 * 
	 * 请你返回至少有多少个学生没有站在正确位置数量。该人数指的是：能让所有学生以 非递减 高度排列的必要移动人数。
	 * 
	 *  
	 * 
	 * 示例：
	 * 
	 * 输入：[1,1,4,2,1,3]
	 * 输出：3
	 * 解释：
	 * 高度为 4、3 和最后一个 1 的学生，没有站在正确的位置。
	 *  
	 * 
	 * 提示：
	 * 
	 * 1 <= heights.length <= 100
	 * 1 <= heights[i] <= 100
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/height-checker
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 
	 * @param heights
	 * @return
	 */
	public int heightChecker(int[] heights) {
		int length = heights.length;
		int[] arr = Arrays.copyOf(heights, length);
		Arrays.sort(arr);
		int cnt = 0;
		for (int i = 0; i < length; i++) {
			if (heights[i] != arr[i]) {
				cnt += 1;
			}
		}
		return cnt;
	}

	/**
	 * (done)1089. 复写零
	 * 
	 * 给你一个长度固定的整数数组 arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
	 * 
	 * 注意：请不要在超过该数组长度的位置写入元素。
	 * 
	 * 要求：请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
	 * 
	 *  
	 * 
	 * 示例 1：
	 * 
	 * 输入：[1,0,2,3,0,4,5,0]
	 * 输出：null
	 * 解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]
	 * 示例 2：
	 * 
	 * 输入：[1,2,3]
	 * 输出：null
	 * 解释：调用函数后，输入的数组将被修改为：[1,2,3]
	 *  
	 * 
	 * 提示：
	 * 
	 * 1 <= arr.length <= 10000
	 * 0 <= arr[i] <= 9
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/duplicate-zeros
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 
	 * @param arr
	 */
	public void duplicateZeros(int[] arr) {
		int left = 0;
		int right = 0;
		int len = arr.length;

		while (right <= len - 1) {
			if (right == len - 1) {
				arr[right--] = arr[left--];
				break;
			}
			if (arr[left] == 0) {
				if (right + 2 > len - 1) {
					arr[right + 1] = 0;
					arr[right] = 0;
					right--;
					left--;
					break;
				} else {
					right += 2;
					left++;
				}
			} else {
				left++;
				right++;
			}
		}
		while (right > left) {
			if (arr[left] == 0) {
				arr[right] = 0;
				arr[right - 1] = 0;
				right -= 2;
				left--;
			} else {
				arr[right--] = arr[left--];
			}
		}
	}

	/**
	 * (done)1122. 数组的相对排序
	 * 
	 * 给你两个数组，arr1 和 arr2，
	 * 
	 * arr2 中的元素各不相同
	 * arr2 中的每个元素都出现在 arr1 中
	 * 对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
	 * 
	 *  
	 * 
	 * 示例：
	 * 
	 * 输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
	 * 输出：[2,2,2,1,4,3,3,9,6,7,19]
	 *  
	 * 
	 * 提示：
	 * 
	 * arr1.length, arr2.length <= 1000
	 * 0 <= arr1[i], arr2[i] <= 1000
	 * arr2 中的元素 arr2[i] 各不相同
	 * arr2 中的每个元素 arr2[i] 都出现在 arr1 中
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/relative-sort-array
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 
	 * @param arr1
	 * @param arr2
	 * @return
	 */
	public int[] relativeSortArray(int[] arr1, int[] arr2) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < arr2.length; i++) {
			map.put(arr2[i], 0);
		}
		int[] arr3 = new int[arr1.length];
		int idx3 = 0;
		for (int i = 0; i < arr1.length; i++) {
			if (map.containsKey(arr1[i])) {
				map.put(arr1[i], map.get(arr1[i]) + 1);
			} else {
				arr3[idx3++] = arr1[i];
			}
		}
		Arrays.sort(arr3, 0, idx3);
		int[] arr4 = new int[arr1.length];
		int idx4 = 0;
		for (int i = 0; i < arr2.length; i++) {
			for (int j = 0; j < map.get(arr2[i]); j++) {
				arr4[idx4++] = arr2[i];
			}
		}
		for (int i = 0; i < idx3; i++) {
			arr4[idx4++] = arr3[i];
		}
		return arr4;
	}

	public int[] relativeSortArray2(int[] arr1, int[] arr2) {
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < arr2.length; i++) {
			map.put(arr2[i], 0);
		}
		int[] arr3 = new int[arr1.length];
		int idx3 = 0;
		for (int i = 0; i < arr1.length; i++) {
			if (map.containsKey(arr1[i])) {
				map.put(arr1[i], map.get(arr1[i]) + 1);
				arr3[idx3++] = -1;
			} else {
				arr3[idx3++] = arr1[i];
			}
		}
		Arrays.sort(arr3);
		idx3 = 0;
		for (int i = 0; i < arr2.length; i++) {
			for (int j = 0; j < map.get(arr2[i]); j++) {
				arr3[idx3++] = arr2[i];
			}
		}
		return arr3;
	}

	/**
	 * (done)1128. 等价多米诺骨牌对的数量
	 * 
	 * 给你一个由一些多米诺骨牌组成的列表 dominoes。
	 * 
	 * 如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。
	 * 
	 * 形式上，dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等价的前提是 a==c 且 b==d，或是 a==d 且 b==c。
	 * 
	 * 在 0 <= i < j < dominoes.length 的前提下，找出满足 dominoes[i] 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。
	 * 
	 *  
	 * 
	 * 示例：
	 * 
	 * 输入：dominoes = [[1,2],[2,1],[3,4],[5,6]]
	 * 输出：1
	 *  
	 * 
	 * 提示：
	 * 
	 * 1 <= dominoes.length <= 40000
	 * 1 <= dominoes[i][j] <= 9
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/number-of-equivalent-domino-pairs
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 
	 * @param dominoes
	 * @return
	 */
	public int numEquivDominoPairs(int[][] dominoes) {
		Map<Domino, Integer> map = new HashMap<Domino, Integer>();
		for (int i = 0; i < dominoes.length; i++) {
			Domino domino = new Domino(Math.min(dominoes[i][0], dominoes[i][1]),
					Math.max(dominoes[i][0], dominoes[i][1]));
			map.put(domino, map.get(domino) == null ? 1 : map.get(domino) + 1);
		}
		int count = 0;
		for (Integer cnt : map.values()) {
			count += cnt * (cnt - 1) / 2;
		}
		return count;
	}

	// BETTER SOLUTION
	public int numEquivDominoPairs2(int[][] dominoes) {
		// 利用好前提条件 1 <= dominoes[i][j] <= 9
		// cnts[i]用于记录i出现的次数
		int[] cnts = new int[100];
		for (int i = 0; i < dominoes.length; i++) {
			int min = dominoes[i][0], max = dominoes[i][1];
			if (min > max) {
				min = dominoes[i][1];// 十位
				max = dominoes[i][0];// 个位
			}
			cnts[min * 10 + max]++;
		}
		int count = 0;
		for (Integer cnt : cnts) {
			count += cnt * (cnt - 1) / 2;
		}
		return count;
	}
	
	class Domino{
		private int min;
		private int max;
		public Domino(int min, int max) {
			super();
			this.min = min;
			this.max = max;
		}
		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + max;
			result = prime * result + min;
			return result;
		}
		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			Domino other = (Domino) obj;
			if (max != other.max)
				return false;
			if (min != other.min)
				return false;
			return true;
		}
	}

	/**
	 * (done)1170. 比较字符串最小字母出现频次
	 * 
	 * 我们来定义一个函数 f(s)，其中传入参数 s 是一个非空字符串；该函数的功能是统计 s  中（按字典序比较）最小字母的出现频次。
	 * 
	 * 例如，若 s = "dcce"，那么 f(s) = 2，因为最小的字母是 "c"，它出现了 2 次。
	 * 
	 * 现在，给你两个字符串数组待查表 queries 和词汇表 words，请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是满足 f(queries[i]) < f(W) 的词的数目，W 是词汇表 words 中的词。
	 * 
	 *  
	 * 
	 * 示例 1：
	 * 
	 * 输入：queries = ["cbd"], words = ["zaaaz"]
	 * 输出：[1]
	 * 解释：查询 f("cbd") = 1，而 f("zaaaz") = 3 所以 f("cbd") < f("zaaaz")。
	 * 示例 2：
	 * 
	 * 输入：queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
	 * 输出：[1,2]
	 * 解释：第一个查询 f("bbb") < f("aaaa")，第二个查询 f("aaa") 和 f("aaaa") 都 > f("cc")。
	 *  
	 * 
	 * 提示：
	 * 
	 * 1 <= queries.length <= 2000
	 * 1 <= words.length <= 2000
	 * 1 <= queries[i].length, words[i].length <= 10
	 * queries[i][j], words[i][j] 都是小写英文字母
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/compare-strings-by-frequency-of-the-smallest-character
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 
	 * @param queries
	 * @param words
	 * @return
	 */
	public int[] numSmallerByFrequency(String[] queries, String[] words) {
		int[] queryCnts = new int[queries.length];
		for (int i = 0; i < queries.length; i++) {
			queryCnts[i] = getCntOfPriorCh(queries[i]);
		}
		int[] wordCnts = new int[words.length];
		for (int i = 0; i < words.length; i++) {
			wordCnts[i] = getCntOfPriorCh(words[i]);
		}
		// numCnts[k]表示wordCnts中比k+1大的元素的个数
		int[] numCnts = new int[10];
		for (int i = 0; i < wordCnts.length; i++) {
			for (int j = wordCnts[i] - 1; j >= 1; j--) {
				numCnts[j - 1]++;
			}
		}
		int[] rets = new int[queries.length];
		for (int i = 0; i < queries.length; i++) {
			rets[i] = numCnts[queryCnts[i] - 1];
		}
		return rets;
	}
	
	public int getCntOfPriorCh(String str) {
		int[] cnts = new int[26];
		for (int i = 0; i < str.length(); i++) {
			cnts[str.charAt(i) - 'a']++;
		}
		for (int i = 0; i < cnts.length; i++) {
			if (cnts[i] != 0) {
				return cnts[i];
			}
		}
		return 0;
	}
}
